{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Top K Frequent Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #hash-table #string #bucket-sort #counting #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #哈希表 #字符串 #桶排序 #计数 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: topKFrequent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #前K个高频单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个单词列表&nbsp;<code>words</code>&nbsp;和一个整数 <code>k</code> ，返回前&nbsp;<code>k</code><em>&nbsp;</em>个出现次数最多的单词。</p>\n",
    "\n",
    "<p>返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， <strong>按字典顺序</strong> 排序。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> words = [\"i\", \"love\", \"leetcode\", \"i\", \"love\", \"coding\"], k = 2\n",
    "<strong>输出:</strong> [\"i\", \"love\"]\n",
    "<strong>解析:</strong> \"i\" 和 \"love\" 为出现次数最多的两个单词，均为2次。\n",
    "    注意，按字母顺序 \"i\" 在 \"love\" 之前。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [\"the\", \"day\", \"is\", \"sunny\", \"the\", \"the\", \"the\", \"sunny\", \"is\", \"is\"], k = 4\n",
    "<strong>输出:</strong> [\"the\", \"is\", \"sunny\", \"day\"]\n",
    "<strong>解析:</strong> \"the\", \"is\", \"sunny\" 和 \"day\" 是出现次数最多的四个单词，\n",
    "    出现次数依次为 4, 3, 2 和 1 次。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= words[i] &lt;= 10</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;由小写英文字母组成。</li>\n",
    "\t<li><code>k</code> 的取值范围是&nbsp;<code>[1, <strong>不同</strong> words[i] 的数量]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>尝试以&nbsp;<code>O(n log k)</code> 时间复杂度和&nbsp;<code>O(n)</code> 空间复杂度解决。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [top-k-frequent-words](https://leetcode.cn/problems/top-k-frequent-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [top-k-frequent-words](https://leetcode.cn/problems/top-k-frequent-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"i\",\"love\",\"leetcode\",\"i\",\"love\",\"coding\"]\\n2', '[\"the\",\"day\",\"is\",\"sunny\",\"the\",\"the\",\"the\",\"sunny\",\"is\",\"is\"]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        eles, counts = numpy.unique(numpy.array(nums), return_counts = True)\n",
    "        topk_index = numpy.argsort(counts)[len(counts)-k:]\n",
    "        return eles[list(topk_index)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        memo = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in memo:\n",
    "                memo[nums[i]] += 1\n",
    "            else:\n",
    "                memo[nums[i]] = 1\n",
    "            \n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            max_ele = max(memo, key=memo.get)\n",
    "            res.append(max_ele)\n",
    "            del memo[max_ele]\n",
    "            \n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        s=[]\n",
    "        m=Counter(nums)\n",
    "        a=sorted(m.items(),key=operator.itemgetter(1),reverse=True)\n",
    "        #print(a)\n",
    "        for i,j in a:\n",
    "            s.append(i)\n",
    "            k-=1\n",
    "            if k==0:\n",
    "                break\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        d = dict()\n",
    "        for i in range(len(nums)):\n",
    "            d[nums[i]] = d.get(nums[i],0)+1\n",
    "        l = [0]*(len(nums)+1)\n",
    "        for i in d:\n",
    "            if d[i]!=0:\n",
    "                if l[d[i]]==0:\n",
    "                    l[d[i]]=[]\n",
    "                l[d[i]].append(i)\n",
    "        res = []\n",
    "        for i in range(len(l)-1,-1,-1):\n",
    "            if not l[i]:\n",
    "                continue\n",
    "            if len(res)<k :\n",
    "                res.extend(l[i])\n",
    "                if len(res)==k:\n",
    "                    return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        if len(nums) <= 0:\n",
    "            return []\n",
    "        temp_dict = {}\n",
    "        for item in nums:\n",
    "            temp_dict[item] = temp_dict.get(item, 0) + 1\n",
    "        temp_list = [0] * (max(list(temp_dict.values())) + 1)\n",
    "        for key, value in temp_dict.items():\n",
    "            if isinstance(temp_list[value], list):\n",
    "                temp_list[value].append(key)\n",
    "            else:\n",
    "                temp_list[value] = [key]\n",
    "        result = []\n",
    "        for value in reversed(temp_list):\n",
    "            if isinstance(value, list):\n",
    "                if k <= 0:\n",
    "                    break\n",
    "                else:\n",
    "                    if len(value) > k:\n",
    "                        result.extend(value[0:len(value) - k])\n",
    "                        break\n",
    "                    else:\n",
    "                        result.extend(value)\n",
    "                        k -= len(value)\n",
    "        # result = sorted(result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        look={}\n",
    "        wei=['*']*(len(nums)+1)\n",
    "        for num in nums:\n",
    "            look[num]=look.get(num,0)+1\n",
    "        for key,v in look.items():\n",
    "            if wei[v]=='*':\n",
    "                wei[v]=[]\n",
    "            wei[v].append(key)\n",
    "        res=[]\n",
    "        print(wei)\n",
    "        for i in wei[::-1]:\n",
    "            if len(res)>=k:\n",
    "                break\n",
    "            if i!='*':\n",
    "                res+=i\n",
    "                \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        \n",
    "        d={}\n",
    "        res=[]\n",
    "        ans=[]\n",
    "        buckets=[[]for _ in range(len(nums)+1)]\n",
    "        \n",
    "        for num in nums:\n",
    "            d[num]=d.get(num,0)+1\n",
    "        for key in d:\n",
    "            res.append((d[key],key))\n",
    "        for t in res:\n",
    "            freq,key=t\n",
    "            buckets[freq].append(key)\n",
    "        buckets.reverse()\n",
    "        \n",
    "        for item in buckets:\n",
    "            if item and k>0:\n",
    "                while item and k>0:\n",
    "                    ans.append(item.pop())\n",
    "                    k-=1\n",
    "                if k==0:\n",
    "                    return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        counts = collections.Counter(nums)\n",
    "        buckets = [[] for _ in range(len(nums) + 1)]    \n",
    "        for num in counts.keys():\n",
    "            buckets[counts[num]].append(num)\n",
    "        ans = []\n",
    "        for i in range(len(nums), 0, -1):      \n",
    "            ans += buckets[i]      \n",
    "            if len(ans) == k: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        m = {}\n",
    "        for n in nums:\n",
    "            if n in m:\n",
    "                m[n] += 1\n",
    "                continue\n",
    "            m[n] = 1\n",
    "\n",
    "        buckets = [[] for i in range(len(nums))]\n",
    "        for key, val in m.items():\n",
    "            buckets[val - 1].append(key)\n",
    "\n",
    "        res = []\n",
    "        for bucket in buckets[::-1]:\n",
    "            for bucket_num in bucket:\n",
    "                if len(res) == k:\n",
    "                    return res\n",
    "                res.append(bucket_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        return [key for key,value in collections.Counter(nums).most_common(k)]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "#         if nums == []:\n",
    "#             return []\n",
    "#         nums.sort()\n",
    "#         s = set()\n",
    "#         start = 0\n",
    "#         dic = {}\n",
    "#         for i in range(len(nums)):\n",
    "#             s.add(nums[i])\n",
    "        \n",
    "#         s = list(s)\n",
    "#         s.sort()\n",
    "#         for e in s:\n",
    "#             freq = 0\n",
    "#             while start < len(nums) and nums[start] == e:\n",
    "#                 freq += 1\n",
    "#                 start += 1\n",
    "#             dic[e] = freq\n",
    "        \n",
    "#         items = dic.items()\n",
    "#         backitems = [[v[1],v[0]] for v in items]\n",
    "#         backitems.sort()\n",
    "        \n",
    "#         return [k for [f,k] in backitems[len(backitems)-k:]]\n",
    "        count = collections.Counter(nums)   \n",
    "        return heapq.nlargest(k, count.keys(), key=count.get)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        if nums == []:\n",
    "            return []\n",
    "        dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in dic:\n",
    "                dic[nums[i]] += 1\n",
    "            else:\n",
    "                dic[nums[i]] = 1\n",
    "        b = [[v[1],v[0]] for v in dic.items()]\n",
    "        b.sort()\n",
    "        \n",
    "        return [k for [f,k] in b[len(b)-k:]]\n",
    "        # count = collections.Counter(nums)   \n",
    "        # return heapq.nlargest(k, count.keys(), key=count.get)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = collections.Counter(nums)\n",
    "        return [a[0] for a in dic.most_common(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic={}\n",
    "        while nums:\n",
    "           i= nums.pop()\n",
    "           if i in dic:\n",
    "               continue\n",
    "           else:\n",
    "                dic[i]=nums.count(i)+1\n",
    "        l=[]\n",
    "    \n",
    "        for zzz in range(k):\n",
    "            max=1\n",
    "            key=1\n",
    "            for j in dic:\n",
    "              if dic[j]>=max:\n",
    "                  max=dic[j]\n",
    "                  key=j\n",
    "            dic.pop(key)\n",
    "            l.append(key)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        result,fre_all = [], []\n",
    "        frequency = 0\n",
    "        n = len(nums)\n",
    "        while nums:\n",
    "            i = 0\n",
    "            while i < len(nums):\n",
    "                if i == 0:\n",
    "                    result.append(nums[i])\n",
    "                    frequency += 1\n",
    "                else:\n",
    "                    if nums[i] != nums[0]:\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    else:\n",
    "                        frequency += 1\n",
    "                        nums.pop(i)\n",
    "                        i -= 1\n",
    "                i += 1\n",
    "            nums.pop(0)\n",
    "            fre_all.append(frequency)\n",
    "            frequency = 0\n",
    "        return self.findk(result, fre_all, k)\n",
    "\n",
    "    def findk(self, nums1, nums2, k):\n",
    "        n = len(nums2)\n",
    "        for i in range(n):\n",
    "            for j in range(1, n-i-1):\n",
    "                if nums2[j] > nums2[j-1]:\n",
    "                    nums2[j], nums2[j-1] = nums2[j-1], nums2[j]\n",
    "                    nums1[j], nums1[j-1] = nums1[j-1], nums1[j]\n",
    "        return nums1[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i not in dic :\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        lst=[]\n",
    "        for element in dic.values():\n",
    "            lst.append(element)\n",
    "        lst.sort(reverse=True)\n",
    "        c=lst[k-1]\n",
    "        lst2=[]\n",
    "        for key,value in dic.items():\n",
    "            if value>=c:\n",
    "                lst2.append(key)\n",
    "        return lst2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        dicList = [(i, dic[i]) for i in dic]\n",
    "\n",
    "        # build a heap\n",
    "        for i in range(k // 2, -1, -1):\n",
    "            self.buildHeap(dicList, i, k)\n",
    "\n",
    "        # adjust the heap\n",
    "        for j in range(k, len(dicList)):\n",
    "            if dicList[j][1] > dicList[0][1]:\n",
    "                dicList[j], dicList[0] = dicList[0], dicList[j]\n",
    "                self.buildHeap(dicList, 0, k)\n",
    "        return [s[0] for s in dicList[:k]]\n",
    "\n",
    "    def buildHeap(self, dicList, start, end):\n",
    "        left = start * 2 + 1\n",
    "        right = left + 1\n",
    "        min_pos = start\n",
    "        if left < end and dicList[left][1] < dicList[start][1]:\n",
    "            min_pos = left\n",
    "        if right < end and dicList[right][1] < dicList[min_pos][1]:\n",
    "            min_pos = right\n",
    "        if min_pos != start:\n",
    "            dicList[min_pos], dicList[start] = dicList[start], dicList[min_pos]\n",
    "            self.buildHeap(dicList, min_pos, end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        count_dict = {}\n",
    "        for n in nums:\n",
    "            if n in count_dict.keys():\n",
    "                continue\n",
    "            count_dict[n] = {'number':n,'total':nums.count(n)}\n",
    "        count_list = list(count_dict.values())\n",
    "        count_list = sorted(count_list,key=lambda x:x['total'],reverse=True)\n",
    "        ans = []\n",
    "        for count_dict in count_list[:k]:\n",
    "            ans.append(count_dict['number'])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def quick(a):\n",
    "            n = len(a)\n",
    "            if n <= 1:\n",
    "                return a\n",
    "            cur, p1, p2 = 0, 0, n - 1\n",
    "#             p1 位置比cur 小 ， p2 >=cur \n",
    "            while p1 < p2:\n",
    "                while p1 <= p2 and a[cur][1] <= a[p1][1]:\n",
    "                    p1 += 1\n",
    "                while a[cur][1] > a[p2][1]:\n",
    "                    p2 -= 1\n",
    "                if p1 < p2:\n",
    "                    a[p1], a[p2] = a[p2], a[p1]\n",
    "            a[cur], a[p2] = a[p2], a[cur]\n",
    "            return quick(a[:p2]) + [a[p2]] + quick(a[p1:])\n",
    "        counter = collections.Counter(nums)\n",
    "        nums = [ele for ele in counter.items()]\n",
    "\n",
    "        res = quick(nums)\n",
    "        return [ele[0] for ele in res[:k]]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        while len(set(nums)) > k:\n",
    "            for num in set(nums):\n",
    "                nums.remove(num)\n",
    "        return list(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        while len(set(nums)) > k:\n",
    "            for num in set(nums):\n",
    "                nums.remove(num)\n",
    "        return list(set(nums))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        mp=dict(collections.Counter(nums))\n",
    "        mp=sorted(mp, key=lambda x: mp[x], reverse=True)\n",
    "        ans=[i for i in mp]\n",
    "        ans=ans[:k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        if(k == len(nums)):\n",
    "            return nums\n",
    "        nums_dict = defaultdict(int)\n",
    "        for item in nums:\n",
    "            nums_dict[item] += 1\n",
    "        topk = [[0,0] for i in range(k)]\n",
    "        heapq.heapify(topk)\n",
    "        for k,v in nums_dict.items():\n",
    "            if topk[0][0] < v:\n",
    "                heapq.heappop(topk)\n",
    "                heapq.heappush(topk,[v,k])\n",
    "        ret = [item[1] for item in topk]\n",
    "        return ret \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        coun = collections.Counter(nums)\n",
    "        res = []\n",
    "        orderd_coun = sorted(coun.items(), key=lambda x:x[1],reverse=True)\n",
    "        j = 0\n",
    "        for i in range(k):\n",
    "            res.append(orderd_coun[j][0])\n",
    "            j+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        # cnt=Counter(nums)\n",
    "        # print(cnt)\n",
    "        # if len(nums)==k: return nums\n",
    "        ans=[]\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else: dic[i]=1\n",
    "        # print(dic)\n",
    "        hp=[]\n",
    "#堆排序\n",
    "        for key,v in dic.items():\n",
    "            heapq.heappush(hp,(v,key))\n",
    "            while len(hp) > k:\n",
    "                heapq.heappop(hp)\n",
    "\n",
    "        # for k, v in dic.items():\n",
    "        #     heapq.heappush(hp,(v,k))\n",
    "        #     #最小的在最前面     \n",
    "        #     while len(hp)>k:\n",
    "        #         heapq.heappop(hp)\n",
    "        # print(hp)\n",
    "        for i in hp:\n",
    "            ans.append(i[1])\n",
    "        return ans            \n",
    "        \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        map = {}\n",
    "        for num in nums:\n",
    "            map[num] = map.get(num, 0) + 1\n",
    "        \n",
    "        pri_que = []\n",
    "        for key, freq in map.items():\n",
    "            print(key, freq)\n",
    "            heapq.heappush(pri_que, (freq, key))\n",
    "            if len(pri_que) > k:\n",
    "                heapq.heappop(pri_que)\n",
    "        for key, freq in map.items():\n",
    "            print(key, freq)\n",
    "        ans = [0]*k\n",
    "        for i in range(k-1, -1, -1):\n",
    "            ans[i] = heapq.heappop(pri_que)[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            if num in dic:\n",
    "                dic[num] += 1\n",
    "            else:\n",
    "                dic[num] = 1\n",
    "        # lis = []\n",
    "        # for ch in dic:\n",
    "        #     lis.append((ch,dic[ch]))\n",
    "        # lis = sorted(lis,key=lambda x:-x[1])\n",
    "        # return [lis[i][0] for i in range(k)]\n",
    "        dic = sorted(dic.items(),key=lambda x:x[1],reverse=True)\n",
    "        return [dic[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        res=dict()\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            res[nums[i]]=res.get(nums[i],0)+1\n",
    "\n",
    "        arr=[]\n",
    "\n",
    "        for key,value in res.items():\n",
    "            heapq.heappush(arr,(value,key))\n",
    "            if len(arr)>k:\n",
    "                heapq.heappop(arr)\n",
    "\n",
    "        ans=[0]*k\n",
    "        for i in range(k-1,-1,-1):\n",
    "            ans[i]=heapq.heappop(arr)[1]\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 使用最小堆\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_count = Counter(nums)\n",
    "        pq = list()\n",
    "        i = 0\n",
    "        for key, val in num_count.items():\n",
    "            if i < k:\n",
    "                heapq.heappush(pq, [val, key])\n",
    "            else:\n",
    "                heapq.heappushpop(pq, [val, key])\n",
    "            i += 1\n",
    "\n",
    "        return [key for _, key in pq]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        fre = {}\n",
    "        for i in nums:\n",
    "            if i in fre:\n",
    "                fre[i] += 1\n",
    "            else:\n",
    "                fre[i] = 1\n",
    "        \n",
    "        keys = list(fre.keys())\n",
    "        keys.sort(key=lambda x: fre[x], reverse=True)\n",
    "        return keys[:k]\n",
    "        # return [i for i, _ in collections.Counter(nums).most_common(k)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        freq_dic = Counter(nums)\n",
    "        hq = []\n",
    "        for key, val in freq_dic.items():\n",
    "            if len(hq) < k:\n",
    "                heapq.heappush(hq, (val, key))\n",
    "            else:\n",
    "                heapq.heappushpop(hq, (val, key))\n",
    "        res = [ele[1] for ele in hq]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        words.sort()\n",
    "        freq = collections.Counter(words)\n",
    "        return [word for word, _ in freq.most_common(k)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        c = Counter(words)\n",
    "        for i in c:\n",
    "            c[i]*=-1\n",
    "        a = sorted(c.keys(),key=lambda x:(c[x],x))\n",
    "        return a[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cnt = Counter(words)\n",
    "        hp = []\n",
    "        for key, value in cnt.items():\n",
    "            heapq.heappush(hp, (-value, key))\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(heapq.heappop(hp)[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        stac_dic = {}\n",
    "        rest_list = []\n",
    "\n",
    "        for x in words:\n",
    "            stac_dic[x] = stac_dic.get(x, 0) + 1\n",
    "\n",
    "        sort_list = sorted(stac_dic.items(), key=lambda x: (-x[1], x[0]), reverse=False)\n",
    "\n",
    "        for x, y in sort_list:\n",
    "            rest_list.append(x)\n",
    "\n",
    "        return rest_list[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        c = {}\n",
    "        for i in words:\n",
    "            c[i]=c.get(i,0)+1\n",
    "        key = lambda x:(-c[x],x)\n",
    "        return heapq.nsmallest(k,c,key)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        from collections import Counter\n",
    "        c_dict = Counter(words)\n",
    "        sorted_words = sorted([(-c_dict[word], word) for word in c_dict])[:k]\n",
    "        return [i[1] for i in sorted_words]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        \"\"\"有序列表\"\"\"\n",
    "        from sortedcontainers import SortedList\n",
    "        n = len(words)\n",
    "        freq2words = [SortedList() for _ in range(n + 1)]\n",
    "        for word, cnt in Counter(words).items():\n",
    "            freq2words[cnt].add(word)\n",
    "        res = []\n",
    "        for i in range(n, 0, -1):\n",
    "            if k >= len(freq2words[i]):\n",
    "                res.extend(freq2words[i])\n",
    "            else:\n",
    "                res.extend(freq2words[i][:k])\n",
    "            k -= len(freq2words[i])\n",
    "            if k <= 0:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        save = {}\n",
    "        for word in words:\n",
    "            if word in save:\n",
    "                save[word]+=1\n",
    "            else:\n",
    "                save[word] = 1\n",
    "        save1 = sorted(save.keys(),key = lambda word: (-save[word],word))\n",
    "        return save1[0:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cnt = collections.Counter(words)\n",
    "\n",
    "        heap = []\n",
    "\n",
    "        for word, freq in cnt.items():\n",
    "            heapq.heappush(heap, (-freq, word))\n",
    "\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(heapq.heappop(heap)[1])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        \n",
    "        val2Freq = dict()\n",
    "        for word in words:\n",
    "            val2Freq[word] = val2Freq.get(word, 0) + 1\n",
    "        \n",
    "        import heapq\n",
    "        max_heap = []\n",
    "        res = []\n",
    "\n",
    "        for key, val in val2Freq.items():\n",
    "            heapq.heappush(max_heap, (-val, key))\n",
    "        \n",
    "        while k > 0:\n",
    "            cur_item = heapq.heappop(max_heap)\n",
    "            res.append(cur_item[1])\n",
    "            k -= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        hash = Counter(words)\n",
    "        res = sorted(hash, key=lambda word:(-hash[word], [word]))\n",
    "        return res[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        \n",
    "        count = collections.Counter(words)\n",
    "        \n",
    "        tem = sorted(count.items(), key=lambda x:(-x[1], x[0]))\n",
    "\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(tem[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        dic={}\n",
    "        for i in words:\n",
    "            dic[i]=dic.get(i,0)+1\n",
    "        new_dic=sorted(dic.items(),key=lambda x:(-x[1],x[0]))\n",
    "        return [w for w,_ in new_dic[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        hash=collections.Counter(words)\n",
    "        ans=sorted(hash,key=lambda word:(-hash[word],word))\n",
    "        return ans[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        # dict_l = collections.Counter(words)\n",
    "        # res = sorted(dict_l, key=lambda word:(-dict_l[word], word))\n",
    "        # return res[:k]\n",
    "        w_d = collections.OrderedDict()\n",
    "        for i in words:\n",
    "            if i in w_d:\n",
    "                w_d[i] += 1\n",
    "            else:\n",
    "                w_d[i] = 1\n",
    "        # a = [(k, v) for k, v in w_d.items()]\n",
    "        # print(a)\n",
    "        w_d = sorted(w_d, key=lambda x: (-w_d[x], x))\n",
    "\n",
    "        return w_d[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        count = Counter(words)\n",
    "        # cntlist = sorted(count.items(), key=lambda e:e[1],reverse=True)\n",
    "        cntlist = sorted(count.items(), key=lambda e:(-e[1], e[0]))\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(cntlist[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        w = Counter(words)\n",
    "        res = sorted(w, key= lambda x:(-w[x], x))\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        dic = defaultdict(int)\n",
    "        for i in words:\n",
    "            dic[i] += 1\n",
    "        wordk = sorted(dic.keys(),key=lambda x: (-dic[x], x))\n",
    "        return wordk[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cc = Counter(words)\n",
    "        sw = sorted(cc.items(),key=lambda item:(-item[1],item[0]))\n",
    "        return [item[0] for item in sw[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        c = {}\n",
    "        for i in words:\n",
    "            c[i] = c.get(i,0)+1\n",
    "        key = lambda x:(-c[x],x)\n",
    "        return heapq.nsmallest(k,c,key)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Word:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "    def __lt__(self, other):\n",
    "        if self.value != other.value:\n",
    "            return self.value < other.value\n",
    "        return self.key > other.key  # 从小到大\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cnt = Counter(words)\n",
    "        hp = []\n",
    "        for key,value in cnt.items():\n",
    "            heapq.heappush(hp,Word(key,value))\n",
    "            while len(hp) > k:\n",
    "                heapq.heappop(hp)\n",
    "        hp.sort(reverse= True)\n",
    "        return [x.key for x in hp]       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        mydict = defaultdict(int)\n",
    "        newWords = []\n",
    "        for word  in words:\n",
    "            if mydict[word] == 0:\n",
    "                newWords.append(word)\n",
    "            mydict[word]  = mydict[word] + 1\n",
    "\n",
    "        myheap = []\n",
    "        heapq.heapify(myheap)\n",
    "        for w in newWords:\n",
    "            heapq.heappush(myheap,(-mydict[w],w))\n",
    "\n",
    "        result = []\n",
    "        for i in range(k):\n",
    "            result.append(heapq.heappop(myheap)[1])\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        f = {}\n",
    "        for i in words:\n",
    "            f[i] = f.get(i,0) + 1\n",
    "        res = sorted(f, key = lambda x:(-f[x], x))\n",
    "        return res[:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        mydict = collections.Counter(words)\n",
    "        L = list(mydict.items())\n",
    "        L = sorted(L, key = lambda d:(-d[1],d[0]))\n",
    "        return [ L[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cnt = collections.Counter(words)\n",
    "\n",
    "        heap = []\n",
    "\n",
    "        for word, freq in cnt.items():\n",
    "            heapq.heappush(heap, (-freq, word))\n",
    "\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(heapq.heappop(heap)[1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 使用最小堆\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        pq = list()\n",
    "        counts = defaultdict(int)\n",
    "        for word in words:\n",
    "            counts[word] += 1\n",
    "        keys = list(counts.keys())\n",
    "        for index, key in enumerate(keys):\n",
    "            # if index < k:\n",
    "            heapq.heappush(pq, (counts[key], key))\n",
    "        # else:\n",
    "        #     heapq.heappushpop(pq, (counts[key], key))\n",
    "        res = list(pq)\n",
    "        res.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [val for _, val in res[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        heap = []\n",
    "        for word, freq in Counter(words).items():\n",
    "            heappush(heap, (-freq, word))\n",
    "        return [heappop(heap)[1] for _ in range(k)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        words_freq = Counter(words)\n",
    "        queue = []\n",
    "\n",
    "        for word, count in words_freq.items():\n",
    "            heapq.heappush(queue, (-count, word))\n",
    "        \n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heapq.heappop(queue)[1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        times = {}\n",
    "        all = []\n",
    "        for word in words:\n",
    "            if word in times:\n",
    "                times[word] += 1\n",
    "                continue\n",
    "            \n",
    "            times[word] = 1\n",
    "            all.append(word)\n",
    "\n",
    "        all.sort(key = lambda x : (-times[x], x))\n",
    "\n",
    "        return all[0:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        count = Counter(words)\n",
    "        countsort= sorted(count.items(), key = lambda x:(-x[1],x[0]))\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(countsort[i][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        from collections import Counter\n",
    "        \n",
    "        hash = Counter(words)\n",
    "        res = sorted(hash, key=lambda word:(-hash[word], word))\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 使用最小堆\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        pq = list()\n",
    "        counts = defaultdict(int)\n",
    "        for word in words:\n",
    "            counts[word] += 1\n",
    "        keys = list(counts.keys())\n",
    "        for _, key in enumerate(keys):\n",
    "            heapq.heappush(pq, (counts[key], key))\n",
    "        res = list(pq)\n",
    "        res.sort(key=lambda x: (-x[0], x[1]))\n",
    "        return [val for _, val in res[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        count = {}\n",
    "        for word in words:\n",
    "            count[word] = count.get(word, 0)+1\n",
    "\n",
    "\n",
    "        minHeap = []\n",
    "        for word,c in count.items():\n",
    "            heapq.heappush(minHeap, (-c, word))\n",
    "        \n",
    "        pairs = heapq.nsmallest(k, minHeap)\n",
    "        return [x[1] for x in pairs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        words_freq = Counter(words)\n",
    "        res = sorted(words_freq, key=lambda x:(-words_freq[x], x))\n",
    "        return res[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        dic = {}\n",
    "        for word in words:\n",
    "            if word not in dic:\n",
    "                dic[word] = 1\n",
    "            else:\n",
    "                dic[word] += 1\n",
    "        nums = list(zip(dic.keys(), dic.values()))\n",
    "        nums.sort(key=lambda x: (-x[1],x[0]))\n",
    "        return [nums[i][0] for i in range(k)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        dp = {}\n",
    "        for word in words:\n",
    "            dp[word] = dp[word] + 1 if word in dp else 1\n",
    "        heap = []\n",
    "        for (word, freq) in dp.items():\n",
    "            heappush(heap, (-freq, word))\n",
    "\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heappop(heap)[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        counts = {}\n",
    "        for w in words:\n",
    "            counts[w] = counts.get(w, 0) + 1\n",
    "\n",
    "        q = []\n",
    "        for w, c in counts.items():\n",
    "            heapq.heappush(q, (c, w))\n",
    "\n",
    "        ret = []\n",
    "        while q:\n",
    "            r = []\n",
    "            prev = q[0][0]\n",
    "            while q and q[0][0] == prev:\n",
    "                c, w = heapq.heappop(q)\n",
    "                r.append(w)\n",
    "            ret.extend(r[::-1])\n",
    "        return ret[::-1][:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        c = {}\n",
    "        for i in words:\n",
    "            c[i] = c.get(i,0)+1\n",
    "        key = lambda x:(-c[x],x)\n",
    "        return heapq.nsmallest(k,c,key)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Word:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "    def __lt__(self, other):\n",
    "        if self.value != other.value:\n",
    "            return self.value < other.value\n",
    "        return self.key > other.key  # 从小到大\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cnt = Counter(words)\n",
    "        hp = []\n",
    "        for key,value in cnt.items():\n",
    "            heapq.heappush(hp,Word(key,value))\n",
    "            while len(hp) > k:\n",
    "                heapq.heappop(hp)\n",
    "        res = deque([])\n",
    "        hp.sort(reverse= True) # klogk\n",
    "        return [x.key for x in hp] \n",
    "        \n",
    "        # O(klogk)\n",
    "        # for _ in range(k):\n",
    "        #     res.appendleft(heappop(hp).key)\n",
    "        # return list(res)  # O(k)      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 排序\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        count_words = Counter(words)\n",
    "        res = sorted(count_words, key=lambda x: (-count_words[x], x))\n",
    "        return res[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cnt = collections.Counter(words)\n",
    "\n",
    "        heap = []\n",
    "\n",
    "        for word, freq in cnt.items():\n",
    "            heapq.heappush(heap, (-freq, word))\n",
    "\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heapq.heappop(heap)[1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        hash = collections.Counter(words)\n",
    "        res = sorted(hash, key=lambda word:(-hash[word], word))\n",
    "        return res[:k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        hash = collections.Counter(words)\n",
    "        # print(hash)\n",
    "        # 词频倒序， 字母正序\n",
    "        res = sorted(hash, key=lambda word:(-hash[word], word))\n",
    "        # print(res)\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        counter = Counter(words)\n",
    "        result = sorted(counter.keys(), key=lambda i: (-counter[i], i))\n",
    "        return result[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        cnt = Counter(words)\n",
    "        ans = sorted(([k, v] for k, v in cnt.items()), key=lambda x: (-x[1], x[0]))\n",
    "        return [x[0] for x in ans][:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        hash = collections.Counter(words)\n",
    "        res = sorted(hash, key=lambda word:(-hash[word], word))\n",
    "        return res[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        hashmap ={}\n",
    "        res = []\n",
    "        for word in words:\n",
    "            hashmap[word] = hashmap.get(word,0)+1\n",
    "        for i,j in sorted(hashmap.items(),key = lambda x:(-x[1],x[0])):\n",
    "            res.append(i)\n",
    "        res_ = res[:k]\n",
    "        return res_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        hash = collections.Counter(words)\n",
    "        res = sorted(hash, key=lambda word:(-hash[word], word))\n",
    "        return res[:k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef topKFrequent(self, words, k):\n",
    "\t\treturn [x for x, _ in Counter(sorted(words)).most_common(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        c = {}\n",
    "        for i in words:\n",
    "            c[i] = c.get(i,0)+1\n",
    "        key = lambda x:(-c[x],x)\n",
    "        return heapq.nsmallest(k,c,key)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        ans=[]\n",
    "        ct=collections.Counter(words)\n",
    "        buckets=[[] for _ in range(len(words)+1)]\n",
    "        for i in ct:\n",
    "            buckets[ct[i]].append(i)\n",
    "        for i in buckets[::-1]:\n",
    "            if(i):\n",
    "                sword=sorted(i)\n",
    "                ans.extend(sword)\n",
    "        return ans[:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        count = Counter(words)\n",
    "        res = []\n",
    "        for i , j in count.items():\n",
    "            res.append([i,j])\n",
    "        res.sort(key = lambda x:(-x[1] , ord(x[0][0]) , x))\n",
    "        list1 = []\n",
    "        for i in range(k):\n",
    "            list1.append(res[i][0])\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        dict1={}\n",
    "        l=[]\n",
    "        for i in range(len(words)):\n",
    "            if words[i] not in dict1:\n",
    "                dict1[words[i]]=words.count(words[i])\n",
    "        dict1=sorted(dict1.items(),key=lambda item:(-item[1],item[0]))\n",
    "        return [key for key,_ in dict1[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        c = {}\n",
    "        for i in words:\n",
    "            c[i] = c.get(i,0)+1\n",
    "        key = lambda x:(-c[x],x)\n",
    "        return heapq.nsmallest(k,c,key)   \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[str], k: int) -> List[str]:\n",
    "        temp = []\n",
    "        ans = []\n",
    "        nums_set = set(nums)\n",
    "        # print(nums_set)\n",
    "        for i in nums_set:\n",
    "            temp.append(nums.count(i))\n",
    "        lst = list(zip(temp,nums_set))\n",
    "        # lst.sort(reverse=True)\n",
    "        lst.sort(key=lambda x: (-x[0], x[1]))\n",
    "        # print(lst)\n",
    "        for i in range(k):\n",
    "            ans.append(lst[i][1])\n",
    "        # ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        # Counter + tuple\n",
    "\n",
    "\n",
    "        cnt = Counter(words)\n",
    "        rec = list(cnt.keys())\n",
    "\n",
    "# Counter(words): This creates a Counter object, which is a subclass of the dict class. It counts the occurrences of each element in the iterable words and stores the results as key-value pairs in the dictionary.\n",
    "\n",
    "# list(cnt.keys()): This converts the keys of the cnt dictionary into a list. The keys represent the unique elements (words) in the words iterable.\n",
    "\n",
    "        rec.sort(key=lambda word: (-cnt[word], word))\n",
    "#  the key is a lambda function that returns a tuple (-cnt[word], word). The sorting will be first based on the negation of the count (-cnt[word]), and if there are ties, it will use the word itself (word) to break the tie. \n",
    "        return rec[:k]\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        info = defaultdict(int)\n",
    "        for word in words:\n",
    "            info[word] +=1\n",
    "        res = sorted(info, key=lambda x:(-info[x], x))\n",
    "        return res[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        heap = [[-count, word] for word, count in Counter(words).items()]\n",
    "        heapify(heap)\n",
    "\n",
    "        topk = nsmallest(k, heap)\n",
    "        ans = [i[1] for i in topk]\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        return [x[1] for x in heapq.nsmallest(k, [(v, k) for k, v in collections.Counter(words).items()], key=lambda a: (-a[0], a[1]))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        d = Counter(words)\n",
    "        pq = []\n",
    "        for key, val in d.items():\n",
    "            heappush(pq, (-val, key))\n",
    "        \n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heappop(pq)[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        s = Counter(words)\n",
    "        s = sorted(s, key=lambda x:(-s[x], x))\n",
    "        return s[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        # Counter + tuple\n",
    "        # Counter是dict的subclass，所以也可以直接使用dict+ sort\n",
    "\n",
    "\n",
    "        cnt = Counter(words)\n",
    "        rec = list(cnt.keys())\n",
    "\n",
    "# Counter(words): This creates a Counter object, which is a subclass of the dict class. It counts the occurrences of each element in the iterable words and stores the results as key-value pairs in the dictionary.\n",
    "\n",
    "# list(cnt.keys()): This converts the keys of the cnt dictionary into a list. The keys represent the unique elements (words) in the words iterable.\n",
    "\n",
    "        def sort_key(word):\n",
    "            return (-cnt[word], word)\n",
    "\n",
    "        rec.sort(key=sort_key)\n",
    "\n",
    "        return rec[:k]\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        l1,lst = [],[]\n",
    "        dct = {}\n",
    "        for i in range(len(words)):\n",
    "            if words[i] not in dct:\n",
    "                dct[words[i]] = 1\n",
    "            else:\n",
    "                dct[words[i]] += 1\n",
    "        heapq.heapify(lst)\n",
    "        for word,count in dct.items():\n",
    "            heapq.heappush(lst,(-count,word))\n",
    "        lst.sort(key=lambda x: (x[0], x[1]))\n",
    "        for i in range(k):\n",
    "            l1.append(lst[i][1])\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        from collections import Counter\n",
    "        \n",
    "        hash = Counter(words)\n",
    "        res = sorted(hash, key=lambda word:(-hash[word], word))  # lambda[1] 按字典顺序排序\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        return [x for x,_ in heapq.nsmallest(k, Counter(words).items(), key=lambda x:(-x[1],x[0]))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        # Counter + tuple\n",
    "\n",
    "\n",
    "        cnt = Counter(words)\n",
    "        rec = list(cnt.keys())\n",
    "\n",
    "# Counter(words): This creates a Counter object, which is a subclass of the dict class. It counts the occurrences of each element in the iterable words and stores the results as key-value pairs in the dictionary.\n",
    "\n",
    "# list(cnt.keys()): This converts the keys of the cnt dictionary into a list. The keys represent the unique elements (words) in the words iterable.\n",
    "\n",
    "        def sort_key(word):\n",
    "            return (-cnt[word], word)\n",
    "\n",
    "        rec.sort(key=sort_key)\n",
    "\n",
    "        return rec[:k]\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        h = {}\n",
    "        for i in words:\n",
    "            if i not in h:\n",
    "                h[i] = 1\n",
    "            else:\n",
    "                h[i] += 1\n",
    "\n",
    "        from queue import PriorityQueue\n",
    "        \n",
    "        pq = PriorityQueue()\n",
    "        for b, v in h.items():\n",
    "            pq.put((-1 * v, b))\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            t = pq.get()[1]\n",
    "            ans.append(t)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        # Heap + Hashtable\n",
    "\n",
    "        count = dict()\n",
    "\n",
    "        for word in words:\n",
    "            if word in count:\n",
    "                count[word] += 1\n",
    "            else:\n",
    "                count[word] = 1\n",
    "        \n",
    "        heap = []\n",
    "\n",
    "        for key, value in count.items():\n",
    "            heapq.heappush(heap, Node(key, value))\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        while len(heap) > 0:\n",
    "            temp = heapq.heappop(heap)\n",
    "            res.append(temp.key)\n",
    "\n",
    "        res.reverse()\n",
    "\n",
    "        #注意：The reverse() method of the list in Python reverses the list in place and returns None. Therefore, return res.reverse() will always return None\n",
    "\n",
    "        return res\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "\n",
    "\n",
    "    def __lt__(self, nxt):\n",
    "        return  self.key > nxt.key if self.value == nxt.value else self.value < nxt.value\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        D = {}\n",
    "        for w in words:\n",
    "            if w not in D:\n",
    "                D[w]=0\n",
    "            D[w] += 1\n",
    "        \n",
    "        Res = []\n",
    "        for key in D:\n",
    "            Res.append([key, D[key]])\n",
    "        \n",
    "        Res.sort(key = lambda x:(-x[1],x[0]))\n",
    "        final = []\n",
    "        for i in range(k):\n",
    "            final.append(Res[i][0])\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bubbleSort(self, lst):\n",
    "        length = len(lst)\n",
    "        for i in range(length):\n",
    "            for j in range(length-i-1):\n",
    "                if lst[j][1] > lst[j+1][1]:\n",
    "                    lst[j], lst[j+1] = lst[j+1], lst[j]\n",
    "                elif lst[j][1] == lst[j+1][1] and lst[j][0] < lst[j+1][0]:\n",
    "                    lst[j], lst[j+1] = lst[j+1], lst[j]\n",
    "\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        dic = {}\n",
    "        for num in words:\n",
    "            if num in dic:\n",
    "                dic[num] += 1\n",
    "            else:\n",
    "                dic[num] = 1\n",
    "        \n",
    "        lst = [(k,v) for k,v in dic.items()]\n",
    "        self.bubbleSort(lst)\n",
    "        result = [i[0] for i in lst[::-1][:k]]\n",
    "        print(lst)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        class Word(object):\n",
    "            def __init__(self, word, freq):\n",
    "                self.word = word\n",
    "                self.freq = freq\n",
    "            def __lt__(self, other):\n",
    "                if self.freq > other.freq:\n",
    "                    return False\n",
    "                elif self.freq < other.freq:\n",
    "                    return True\n",
    "                else:\n",
    "                    if self.word > other.word:\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "\n",
    "\n",
    "        import heapq\n",
    "        min_heapq = []\n",
    "        from collections import Counter\n",
    "        word_count = Counter(words)\n",
    "        for word in word_count:\n",
    "            # if word == 'ten' or word == 'bklij':\n",
    "            #     print('now')\n",
    "            now_t = Word(word, word_count[word])\n",
    "            heapq.heappush(min_heapq, now_t)\n",
    "            if len(min_heapq) > k:\n",
    "                heapq.heappop(min_heapq)\n",
    "            # if len(min_heapq) < k:\n",
    "            #     heapq.heappush(min_heapq, now_t)\n",
    "            # else:\n",
    "            #     if now_t > min_heapq[0]:\n",
    "            #         heapq.heappop(min_heapq)\n",
    "            #         heapq.heappush(min_heapq, now_t)\n",
    "        result = []\n",
    "        while len(min_heapq) > 0:\n",
    "            result.append(heapq.heappop(min_heapq).word)\n",
    "        return result[::-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
